using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Text;

namespace Gko.Utils
{
	/// <summary>
	/// Methods for fast binary search in sorted <see cref="T:System.Collections.Generic.IList`1"/>
	/// </summary>
	public static class BinarySearch
	{
		/// <summary>
		/// Finds the specified item in list.
		/// </summary>
		/// <typeparam name="TValue">The type of the value.</typeparam>
		/// <param name="list">The list.</param>
		/// <param name="item">The item.</param>
		/// <returns>Index of item or null if not found</returns>
		public static int? Find<TValue>(this IList<TValue> list, TValue item)
		{
			var startIndex = 0;
			var endIndex = list.Count - 1;
			return list.Find(item, ref startIndex, ref endIndex, null);
		}

		/// <summary>
		/// Finds the specified item in list using comparer.
		/// </summary>
		/// <typeparam name="TValue">The type of the value.</typeparam>
		/// <param name="list">The list.</param>
		/// <param name="item">The item.</param>
		/// <param name="comparer">The comparer.</param>
		/// <returns>Index of item or null if not found</returns>
		public static int? Find<TValue>(this IList<TValue> list, TValue item, IComparer<TValue> comparer)
		{
			var startIndex = 0;
			var endIndex = list.Count - 1;
			return list.Find(item, ref startIndex, ref endIndex, comparer);
		}

		/// <summary>
		/// Finds the specified item in list.
		/// </summary>
		/// <typeparam name="TValue">The type of the value.</typeparam>
		/// <param name="list">The list.</param>
		/// <param name="item">The item.</param>
		/// <param name="startIndex">The start index.</param>
		/// <param name="endIndex">The end index.</param>
		/// <returns>Index of item or null if not found</returns>
		[System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1045:DoNotPassTypesByReference", MessageId = "3#"), System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1045:DoNotPassTypesByReference", MessageId = "2#")]
		public static int? Find<TValue>(this IList<TValue> list, TValue item, ref int startIndex, ref int endIndex)
		{
			return list.Find(item, ref startIndex, ref endIndex, null);
		}

		/// <summary>
		/// Finds the specified item in list using comparer.
		/// </summary>
		/// <typeparam name="TValue">The type of the value.</typeparam>
		/// <param name="list">The list.</param>
		/// <param name="item">The item.</param>
		/// <param name="startIndex">The start index.</param>
		/// <param name="endIndex">The end index.</param>
		/// <param name="comparer">The comparer.</param>
		/// <returns>Index of item or null if not found</returns>
		[System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1045:DoNotPassTypesByReference", MessageId = "3#"), System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1045:DoNotPassTypesByReference", MessageId = "2#")]
		public static int? Find<TValue>(this IList<TValue> list, TValue item, ref int startIndex, ref int endIndex, IComparer<TValue> comparer)
		{
			if(list.IsNull()) {
				throw new ArgumentNullException("list");
			}

			if (list.Count == 0) {
				return null;
			}
			if (startIndex < 0) {
#if SILVERLIGHT
				throw new ArgumentOutOfRangeException("startIndex", "Less than zero. Actual value: {0}".Format(startIndex));
#else
				throw new ArgumentOutOfRangeException("startIndex", startIndex, "Less than zero");
#endif
			}
			if (endIndex >= list.Count) {
#if SILVERLIGHT
				throw new ArgumentOutOfRangeException("endIndex", "Greater than {0}. Actual value: {1}".Format(CultureInfo.CurrentCulture, list.Count, endIndex));
#else
				throw new ArgumentOutOfRangeException("endIndex", endIndex, String.Format(CultureInfo.CurrentCulture, "Greater than {0}", list.Count));
#endif
			}
			if (comparer == null) {
				comparer = Comparer<TValue>.Default;
			}

			if (comparer.Compare(list[startIndex], item) == 0) {
				return startIndex;
			}

			if (comparer.Compare(list[endIndex], item) == 0) {
				return endIndex;
			}

			while (startIndex <= endIndex) {
				var midIndex = startIndex + ((endIndex - startIndex) >> 1);
				var cmp = comparer.Compare(list[midIndex], item);
				if (cmp == 0) {
					return midIndex;
				}
				if (cmp < 0) {
					startIndex = midIndex + 1;
				} else {
					endIndex = midIndex - 1;
				}
			}
			return null;
		}
	}
}